package org.example.day;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/05/17 10:02
 */

//你有 n 个工作和 m 个工人。给定三个数组： difficulty, profit 和 worker ，其中:
//
//
// difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。
// worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。
//
//
// 每个工人 最多 只能安排 一个 工作，但是一个工作可以 完成多次 。
//
//
// 举个例子，如果 3 个工人都尝试完成一份报酬为 $1 的同样工作，那么总收益为 $3 。如果一个工人不能完成任何工作，他的收益为 $0 。
//
//
// 返回 在把工人分配到工作岗位后，我们所能获得的最大利润 。
//
//
//
// 示例 1：
//
//
//输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
//输出: 100
//解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。
//
// 示例 2:
//
//
//输入: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
//输出: 0
//
//
//
// 提示:
//
//
// n == difficulty.length
// n == profit.length
// m == worker.length
// 1 <= n, m <= 10⁴
// 1 <= difficulty[i], profit[i], worker[i] <= 10⁵
//
//
// Related Topics 贪心 数组 双指针 二分查找 排序 👍 133 👎 0

public class Solution826 {

    public static void main(String[] args) {
        Solution826 solution826 = new Solution826();
        int[] difficulty = new int[]{13,37,58};
        int[] profit = new int[]{4,90,96};
        int[] worker = new int[]{34,73,45};
        System.out.println("result:" + solution826.maxProfitAssignment(difficulty, profit, worker));
    }


    // 同一个难度的工作，选择报酬高的  低难度高报酬的，仅保留低难度的
    // 同一个能力的工人，可以选择同一份工作
    // 能力范围内 尽可能做最高难度，最高报酬的工作
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int sum = 0;
        // 挑选工作
        HashMap<Integer, Integer> workMap = new HashMap<>();
        for(int i=0;i<difficulty.length;i++){
            if(workMap.containsKey(difficulty[i])){
                if(profit[i] > workMap.get(difficulty[i])){
                    workMap.put(difficulty[i], profit[i]);
                }
            }else {
                workMap.put(difficulty[i], profit[i]);
            }
        }

        int[] workChoice = new int[workMap.size()];
        int index = 0;
        for(Integer key : workMap.keySet()){
            workChoice[index] = key;
            index++;
        }

        //排序，过滤掉高难度，低报酬工作
        HashMap<Integer, Integer> betterMap = new HashMap<>();
        Arrays.sort(workChoice);
        betterMap.put(workChoice[0], workMap.get(workChoice[0]));
        int max = workMap.get(workChoice[0]);
        for(int i=1;i<workChoice.length;i++){
            if(workMap.get(workChoice[i]) > max){
                betterMap.put(workChoice[i], workMap.get(workChoice[i]));
                max = workMap.get(workChoice[i]);
            }
        }

        //保留最优的工作难度
        workChoice = new int[betterMap.size()];
        index = 0;
        for(Integer key : betterMap.keySet()){
            workChoice[index] = key;
            index++;
        }
        Arrays.sort(workChoice);

        // 分配工作，同能力的分配同一份工作  使用二分查找，快速找到对应的工作
        HashMap<Integer, Integer> choiceMap = new HashMap<>();
        for(int workerSingle : worker){
            int work = -1;
            if(betterMap.containsKey(workerSingle)){
                work = workerSingle;
            }else if(choiceMap.containsKey(workerSingle)){
                work = choiceMap.get(workerSingle);
            }else {
                work = getWorkChoice(workChoice, workerSingle);
                choiceMap.put(workerSingle, work);
            }
            if(betterMap.get(work) != null){
                System.out.println(betterMap.get(work));
                sum += betterMap.get(work);
            }
        }
        return sum;
    }

    private int getWorkChoice(int[] workChoice, int workerSingle) {
        if (workerSingle < workChoice[0]) {
            //不能胜任
            return -1;
        }

        for(int i=1;i<workChoice.length;i++){
            if(workChoice[i] > workerSingle){
                return workChoice[i-1];
            }
        }
        return workChoice[workChoice.length-1];
    }

    private int getWorkChoice2(int[] workChoice, int workerSingle) {
        if(workerSingle < workChoice[0]){
            //不能胜任
            return -1;
        }

        int start = 0;
        int end = workChoice.length - 1;

        while (start <= end){
            int middle = start + (end - start)/2;
            if(workerSingle == workChoice[middle]){
                return workChoice[middle];
            } else if(workerSingle > workChoice[middle]){
                start = middle + 1;
            }else {
                end = middle -1;
            }
        }

        return workChoice[end];
    }

}
